/*************************************************************************
	> File Name: 111.二叉树的最小深度_v2.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/15 12:46:37 2021
 ************************************************************************/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//广搜：自己实现，可以用链表实现队列，更节省空间
//遍历整棵树，当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
struct QueueNode {
    int head, tail;
    struct TreeNode **data;
    int capacity;
};

struct QueueNode *init(int n) {
    struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    node->head = 0;
    node->tail = 0;
    node->data = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * n);
    node->capacity = n;
    return node;
}

int minDepth(struct TreeNode* root){
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    
    struct QueueNode *que = init(100000);
    que->data[(que->tail)++] = root;
    int depth = 1;
    while (que->head != que->tail) {
        int size = (que->tail - que->head); //计算队列中的元素
        for (int i = 0; i < size; i++) { //处理每层的节点
            struct TreeNode *temp = que->data[que->head++];
            if (temp->left != NULL) {
                que->data[(que->tail)++] = temp->left;
            }
            if (temp->right != NULL) {
                que->data[(que->tail)++] = temp->right;
            }

            if (temp->left == NULL && temp->right == NULL) {
                return depth;
            }
        }
        depth++;
    }
    return false;
}
